import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        ListNode head = new ListNode();
        ListNode p = head;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, Comparator.comparingInt(node -> node.val));
        for (ListNode node : lists) {
            if (node != null) {
                queue.add(node);
            }
        }
        while (queue.size() > 0) {
            ListNode node = queue.poll();
            p.next = node;
            p = node;
            if (node.next != null) {
                node = node.next;
                queue.add(node);
            }

        }
        return head.next;
    }
}